package skiplist.java;

import java.util.Random;
import java.util.StringJoiner;

public class SkipList<E extends Comparable<E>> {

    private static final int MAX_LEVEL = 32;

    /**
     * 跳表的头结点
     */
    private SkipListNode<E> head;
    /**
     * 跳表的尾节点
     */
    private SkipListNode<E> tail;

    /*
     * 当前跳表支持的最大级别
     */
    private int levelCount;
    /**
     * 头结点等级索引（从高到低，为levelCount-1...0）
     */
    private int topLevelIndex;

    private int length;

    private final Random random = new Random();





    public SkipList(int levelCount){
        assert levelCount>=0 && levelCount<=MAX_LEVEL;
        this.levelCount = levelCount;
        this.topLevelIndex = levelCount-1;
        this.head = new SkipListNode<E>(null,topLevelIndex);
        this.tail = new SkipListNode<E>(null,topLevelIndex);
        for(int i=0;i<levelCount;i++){
            this.head.nexts[i] = this.tail;
        }
    }

    public int getLevelCount(){
        return this.levelCount;
    }
    /**
     * 跳表是否包含给定元素
     * @param e
     * @return
     */
    public boolean contains(E e){
        SkipListNode<E> p = this.head;
        int i=topLevelIndex;
        for(;i>=0;i--){
            while(p.nexts[i]!=this.tail){
                int cmp = e.compareTo(p.nexts[i].value);
                //当前层，没有找到e值，向下一层
                if(cmp<0){
                    break;
                }
                if(cmp == 0){
                    return true;
                }
                //e应该排在当前值后面，继续搜索
                p = p.nexts[i];
            }
        }
        return false;
    }
    /**
     * 按照论文中的算法，随机分配结点所在层级索引
     * @return
     */
    private int randomLevelIndex(){
        int i = 0;
        for(i=0;i<this.topLevelIndex;i++){
            if(random.nextDouble()<0.5){
                break;
            }
        }
        return  i;
    }
    /**
     * 插入新元素
     */

     public boolean add(E value){
        int level = randomLevelIndex();
        SkipListNode<E>[] preNodes = new SkipListNode[level+1];
        //寻找结点插入位置
        SkipListNode<E> p = head;
        int i = topLevelIndex;
        //先从上到下遍历不需要记录前置结点的层级
        for(;i>level;i--){
            //遍历该层链表，找到位于待插入结点之后的第一个结点
            while(p.nexts[i]!=this.tail){
                int cmp = value.compareTo(p.nexts[i].value);
                //找到了相同元素
                if(cmp == 0){
                    return true;
                }
                //本层遍历结束
                if(cmp<0){
                    break;
                }
                p = p.nexts[i];
            }
        }
        //获取从level到0层的待插入结点的前置结点
        while(i>=0){
            //遍历该层，知道位于待插入结点之后的第一个结点
            while(p.nexts[i]!=this.tail){
                int cmp = value.compareTo(p.nexts[i].value);
                if(cmp<0){
                    break;
                }
                if(cmp==0){
                    return true;
                }
                p = p.nexts[i];
            }
            //当前层已经遍历完成，保存最后一个遍历的结点，它是待插入结点在该层的前置结点
            preNodes[i] = p;
            i--;
        }

        //插入结点
        SkipListNode<E> node = new SkipListNode<>(value,level);
        for(int j=0;j<=level;j++){
            node.nexts[j] =preNodes[j].nexts[j];
            preNodes[j].nexts[j] = node;
        }

        return true;     
     }
     /**
      * 在跳表中移除指定的元素
      * @param value
      * @return 移除成功，返回true;没有找到元素或者移除失败返回false;
      */
     public boolean remove(E value){
        SkipListNode<E> p = head;
        boolean findValue = false;
        for(int i=levelCount-1;i>=0;i--){
            while(p.nexts[i] != tail && value.compareTo(p.nexts[i].value)>0){
                p = p.nexts[i];
            }
            if(p.nexts[i]!=tail && value.compareTo(p.nexts[i].value)==0){
                p.nexts[i] = p.nexts[i].nexts[i];
                findValue = true;
            }
        } 
        if(findValue){
            length--;
        }
        return findValue;
     }

    public void displaySkipList() {
        System.out.println("SkipList:");
        for (int i = levelCount - 1; i >= 0; i--) {
            System.out.print("Level " + i + ": head -> ");
            SkipListNode<E> node = head.nexts[i];
            SkipListNode<E> current = head.nexts[0]; // Start from the bottom level
            while (current != tail) {
                if (node != tail && current.value.equals(node.value)) {
                    // If the current bottom level node is present at this level, print it
                    System.out.print(current.value + " -> ");
                    node = node.nexts[i];
                } else {
                    int valueLength = current.value.toString().length();

                    // If not, print a placeholder to maintain alignment
                    System.out.print("-".repeat(valueLength) + " -> ");
                }
                current = current.nexts[0]; // Move to the next node at the bottom level
            }
            System.out.println("tail");
        }
    }

    public static class SkipListNode<T> {
        T value;
        int levelIndex;
        SkipListNode<T>[] nexts;
        
        public SkipListNode(){}
        public SkipListNode(T value,int levelIndex){
            this.value = value;
            this.levelIndex = levelIndex;
            this.nexts = new SkipListNode[levelIndex+1];

        }
        public SkipListNode(T value,int levelIndex,SkipListNode<T>[] nexts){
            this.value = value;
            this.levelIndex = levelIndex;
            assert nexts != null;
            assert nexts.length >= levelIndex+1;
            this.nexts = new SkipListNode[levelIndex+1];
            for(int i=0;i<levelIndex+1;i++){
                this.nexts[i] = nexts[i];
            }
        }
    
        public T getValue(){
            return this.value;
        }

        public SkipListNode<T>[] getNexts(){
            return this.nexts;
        }

    }

    @Override
    public String toString(){
        SkipListNode<E> p = this.head;
        StringJoiner joiner = new StringJoiner(",", "", "");
        while(p.nexts[0]!=this.tail){
            joiner.add(p.nexts[0].value.toString());
            p = p.nexts[0];
        }
        return joiner.toString();
    }
}

